package main

func solve(board [][]byte) {
	if len(board) == 0 {
		return
	}
	visited := make([][]bool, len(board))
	for i := range visited {
		visited[i] = make([]bool, len(board[0]))
	}
	for i, row := range board {
		for j, v := range row {
			if v == 'O' && !visited[i][j] {
				track := make([][2]int, 0)
				if !bfs(board, visited, i, j, &track) {
					for _, pos := range track {
						board[pos[0]][pos[1]] = 'X'
					}
				}
			}
		}
	}
}

// i,j 必须在范围内
// 返回是否邻接边界
func bfs(board [][]byte, visited [][]bool, i, j int, track *[][2]int) bool {
	visited[i][j] = true
	*track = append(*track, [2]int{i, j})
	posArr := [][2]int{
		{i - 1, j},
		{i + 1, j},
		{i, j - 1},
		{i, j + 1},
	}
	ret := false
	if i == 0 || i == len(board)-1 || j == 0 || j == len(board[0])-1 {
		ret = true
	}
	for _, pos := range posArr {
		x := pos[0]
		y := pos[1]
		if x >= 0 && x < len(board) && y >= 0 && y < len(board[0]) &&
			!visited[x][y] && board[x][y] == 'O' {
			if bfs(board, visited, x, y, track) {
				ret = true
			}
		}
	}
	return ret
}

func main() {
	//board := [][]byte{
	//	{'X', 'X', 'X', 'X'},
	//	{'X', 'O', 'O', 'X'},
	//	{'X', 'X', 'O', 'X'},
	//	{'X', 'O', 'X', 'X'},
	//}
	board := [][]byte{
		{'O', 'O', 'O'},
		{'O', 'O', 'O'},
		{'O', 'O', 'O'},
	}
	solve(board)
	for _, row := range board {
		for _, v := range row {
			print(string(v), " ")
		}
		print("\n")
	}
}
